NGC 205, a close satellite of the M31 galaxy, is our nearest example of a dwarf elliptical galaxy. Photometric and kinematic observations suggest that NGC 205 is undergoing tidal distortion from its interaction with M31. Despite earlier attempts, the orbit and progenitor properties of NGC 205 are not well known. We perform an optimized search for these unknowns by combining a genetic algorithm with restricted N-body simulations of the interaction. This approach, coupled with photometric and kinematic observations as constraints, allows for an effective exploration of the parameter space. We represent NGC 205 as a static Hernquist potential with embedded massless test particles that serve as tracers of surface brightness. We explore 3 distinct, initially stable configurations of test particles: cold rotating disk, warm rotating disk, and hot, pressure-supported spheroid. Each model reproduces some, but not all, of the observed features of NGC 205, leading us to speculate that a rotating progenitor with substantial pressure support could match all of the observables. Furthermore, plausible combinations of mass and scale length for the pressure-supported spheroid progenitor model reproduce the observed velocity dispersion profile. For all 3 models, orbits that best match the observables place the satellite 11+/-9 kpc behind M31 moving at very large velocities: 300-500 km/s on primarily radial orbits. Given that the observed radial component is only 54 km/s, this implies a large tangential motion for NGC 205, moving from the NW to the SE. These results suggest NGC 205 is not associated with the stellar arc observed to the NE of NGC 205. Furthermore, NGC 205's velocity appears to be near or greater than its escape velocity, signifying that the satellite is likely on its first M31 passage.